A skip list is a useful type of data structure for arranging data in a memory space, such as a cache memory of an array controller in a data storage system. A skip list is a form of a linked list where each item, or node, in the list has a random number of extra forward pointers. Searching such a list approximates the performance of searching binary trees, while having dramatically lower cost in terms of maintenance as compared to a binary tree.
Generally, a skip list is maintained in an order based on comparisons of a key field within each node. The comparison is arbitrarily selected and may be ascending or descending, numeric or alpha-numeric, and so forth. When a new node is to be inserted into the list, a mechanism is generally used to assign the number of forward pointers to the node in a substantially random fashion. The number of extra forward pointers associated with each node is referred to as the node level.
While skip lists have been found operable in a number of data structure management applications, there nevertheless remains a continued need for improvements in the art that promote enhanced memory utilization and searching efficiencies. It is to these and other improvements that the claimed invention is generally directed.